package name.huzhenbo.java.algorithm.search;

import java.util.HashMap;
import java.util.Map;

/**
 * If 2 objects are equals (equals method), then they must produce same hashcode.
 *
 * But it does not require 2 not equals objects must produce distinct hashcode (allow conflict, and we need to deal with
 * conflict).
 *
 * We can know if the array contains the element in constant time complexity.
 */
class HashSearcher<T> {
    private T[] input;
    private Map<Integer, T> map;

    public HashSearcher(T[] input) {
        this.input = input;
        init();
    }

    private void init() {
        map = new HashMap<Integer, T>();
        for(T elem: input){
            map.put(elem.hashCode(), elem);
        }
    }

    public boolean exists(T element) {
        T val = map.get(element.hashCode());
        return val != null && val.equals(element);
    }
}
